#define _CRT_SECURE_NO_WARNINGS 1
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
    bool isValid(string s)
    {
        //cerr << s << endl;
        if (s.size() == 0) return true;
        stack<char> st;
        //st.push(s[0]);
        for (int i = 0;i < s.size();++i)
        {
            //cerr<<"s[i]="<<s[i]<<endl;
            if (st.empty())
            {
                st.push(s[i]);
                continue;
            }
            char top = st.top();
            //cerr<<"top="<<top<<endl;
            if ((top == '(' && s[i] == ')') ||
                (top == '[' && s[i] == ']') ||
                (top == '{' && s[i] == '}'))
            {
                st.pop();
            }
            else
            {
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};